{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Array Length After Pair Removals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #two-pointers #binary-search #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #双指针 #二分查找 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minLengthAfterRemovals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除数对后的最小数组长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的 <strong>非递减</strong> 整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以执行以下操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择 <strong>两个&nbsp;</strong>下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;，满足&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>nums[i] &lt; nums[j]</code>&nbsp;。</li>\n",
    "\t<li>将 <code>nums</code>&nbsp;中下标在&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 <strong>0</strong>&nbsp;开始编号。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个整数，表示执行以上操作任意次后（可以执行 <strong>0</strong> 次），<code>nums</code>&nbsp;数组的 <strong>最小</strong>&nbsp;数组长度。</p>\n",
    "\n",
    "<p>请注意，<code>nums</code> 数组是按&nbsp;<strong>非降序&nbsp;</strong>排序的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,4,9]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>一开始，nums = [1, 3, 4, 9] 。\n",
    "第一次操作，我们选择下标 0 和 1 ，满足 nums[0] &lt; nums[1] &lt;=&gt; 1 &lt; 3 。\n",
    "删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。\n",
    "下一次操作，我们选择下标 0 和 1 ，满足 nums[0] &lt; nums[1] &lt;=&gt; 4 &lt; 9 。\n",
    "删除下标 0 和 1 处的元素，nums 变成空数组 [] 。\n",
    "所以，可以得到的最小数组长度为 0 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,6,9]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>一开始，nums = [2, 3, 6, 9] 。\n",
    "第一次操作，我们选择下标 0 和 2 ，满足 nums[0] &lt; nums[2] &lt;=&gt; 2 &lt; 6 。\n",
    "删除下标 0 和 2 处的元素，nums 变成 [3, 9] 。\n",
    "下一次操作，我们选择下标 0 和 1 ，满足 nums[0] &lt; nums[1] &lt;=&gt; 3 &lt; 9 。\n",
    "删除下标 0 和 1 处的元素，nums 变成空数组 [] 。\n",
    "所以，可以得到的最小数组长度为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>一开始，nums = [1, 1, 2] 。\n",
    "第一次操作，我们选择下标 0 和 2 ，满足 nums[0] &lt; nums[2] &lt;=&gt; 1 &lt; 2 。\n",
    "删除下标 0 和 2 处的元素，nums 变成 [1] 。\n",
    "无法对数组再执行操作。\n",
    "所以，可以得到的最小数组长度为 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;是 <strong>非递减</strong>&nbsp;数组。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-array-length-after-pair-removals](https://leetcode.cn/problems/minimum-array-length-after-pair-removals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-array-length-after-pair-removals](https://leetcode.cn/problems/minimum-array-length-after-pair-removals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,9]', '[2,3,6,9]', '[1,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        #O(N)\n",
    "        # a = max(collections.Counter(nums).values())\n",
    "        # n = len(nums)\n",
    "\n",
    "        # if a>=n/2:\n",
    "        #     return 2*a-n\n",
    "        # else:\n",
    "        #     return n%2\n",
    "        #log(n) 找到出现次数的元素个个数\n",
    "        n = len(nums)\n",
    "        mx = nums[n//2]\n",
    "        left,right = 0,n-1\n",
    "        def biset_left(mx):\n",
    "            left,right = 0,n-1\n",
    "            while left<=right:\n",
    "                mid = (left+right)//2\n",
    "                if nums[mid]<mx:\n",
    "                    left =mid+1\n",
    "                else:\n",
    "                    right = mid-1\n",
    "            return left    \n",
    "                   \n",
    "        a = biset_left(mx+1)-biset_left(mx)\n",
    "        if a>=n/2:\n",
    "            return 2*a-n \n",
    "        else:\n",
    "            return n%2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def fun() -> int:\n",
    "            t = nums[n // 2]\n",
    "            cnt = bisect.bisect_right(nums, t) - bisect.bisect_left(nums, t)\n",
    "            return cnt if cnt * 2 > n else -1\n",
    "\n",
    "        m = fun()\n",
    "        if m == -1:\n",
    "            return n % 2\n",
    "        return m - (n - m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r, x = 0, n - 1, nums[n // 2]\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if nums[mid] >= x:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        j = l\n",
    "        r = n - 1\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if nums[mid] <= x:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        i = l\n",
    "\n",
    "        cx = i - j + 1\n",
    "        return max(2 * cx - n, n % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x = nums[n // 2]\n",
    "        max_cnt = bisect_right(nums, x) - bisect_left(nums, x)\n",
    "        return max(max_cnt * 2 - n, n % 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        maxCnt = cnt = 1\n",
    "        pre = nums[0]\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if pre == nums[i]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                maxCnt = max(maxCnt, cnt)\n",
    "                pre = nums[i]\n",
    "                cnt = 1\n",
    "        maxCnt = max(maxCnt, cnt)\n",
    "        if maxCnt * 2 > n:\n",
    "            return maxCnt - (n - maxCnt)\n",
    "        else:\n",
    "            return 0 if n % 2 == 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mid = nums[n // 2]\n",
    "        maxCnt = bisect_right(nums, mid) - bisect_left(nums, mid)\n",
    "        return max(2 * maxCnt - n, n % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "    l = len(nums)\n",
    "    a, b, c = 0, l // 2, l // 2\n",
    "    \n",
    "    d = 0\n",
    "    while a < b and c < l:\n",
    "      if nums[a] != nums[c]:\n",
    "        a += 1\n",
    "        c += 1\n",
    "        d += 2\n",
    "      else:\n",
    "        c = bisect.bisect_left(nums, nums[a] + 1, c)\n",
    "    # print(f\"a{a} b{b} c{c} l{l}\")\n",
    "    return l - d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x = nums[n // 2]\n",
    "        max_cnt = bisect_right(nums, x) - bisect_left(nums, x)\n",
    "        return max(max_cnt * 2 - n, n % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        if l&1:\n",
    "            mid=nums[(l-1)//2]\n",
    "            c=nums.count(mid)\n",
    "            if c>l//2:\n",
    "                return l-(2*(l-c))\n",
    "            else:\n",
    "                return 1\n",
    "        else:\n",
    "            mid1=nums[l//2-1]\n",
    "            mid2=nums[l//2]\n",
    "            if mid1==mid2:\n",
    "                c=nums.count(mid1)\n",
    "                if c>l//2:\n",
    "                    return l-(2*(l-c))\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        x = nums[n//2]\n",
    "        maxCnt = bisect_right(nums, x) - bisect_left(nums, x)\n",
    "        print(maxCnt, n)\n",
    "        if maxCnt * 2 > n:\n",
    "            return maxCnt -(n - maxCnt)\n",
    "        else:\n",
    "            return n%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pq = []\n",
    "        for i in range(n // 2):\n",
    "            heapq.heappush(pq, nums[i])\n",
    "        \n",
    "        for i in range(n // 2, n):\n",
    "            if pq and nums[i] > pq[0]:\n",
    "                heapq.heappop(pq)\n",
    "            else:\n",
    "                heapq.heappush(pq, nums[i])\n",
    "        return len(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def fun() -> int:\n",
    "            t = 0\n",
    "            cnt = 0\n",
    "            for x in nums:\n",
    "                if cnt == 0:\n",
    "                    cnt += 1\n",
    "                    t = x\n",
    "                    continue\n",
    "                if x == t:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "            cnt = sum([t == x for x in nums])\n",
    "            return cnt if cnt > n // 2 else -1\n",
    "\n",
    "        m = fun()\n",
    "        if m == -1:\n",
    "            return n % 2\n",
    "        return m - (n - m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        ret=[]\n",
    "        left=0\n",
    "        right=0\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 1\n",
    "        while right<n:\n",
    "            if nums[right]==nums[left]:\n",
    "                right+=1\n",
    "            else:\n",
    "                left=right\n",
    "                right+=1\n",
    "            ret.append(right-left)    \n",
    "        k=max(ret)\n",
    "        if 2*k-n<0:\n",
    "            if n%2==0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        return 2*k-n\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        cnt = [1]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i - 1]:\n",
    "                cnt[-1] += 1\n",
    "            else:\n",
    "                cnt.append(1)\n",
    "        if len(cnt) == 1:\n",
    "            return cnt[0]\n",
    "        mx = max(cnt)\n",
    "        sm = sum(cnt)\n",
    "        if sm // 2 < mx:\n",
    "            return mx - (sm - mx)\n",
    "        else:\n",
    "            return sm % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        ds = []\n",
    "        d = 1\n",
    "        c = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == c:\n",
    "                d += 1\n",
    "            else:\n",
    "                ds.append(d)\n",
    "                d = 1\n",
    "                c = nums[i]\n",
    "        ds.append(d)\n",
    "        \n",
    "        max_d = max(ds)\n",
    "        if sum(ds) - max_d <= max_d:\n",
    "            return max_d + max_d -sum(ds)\n",
    "        else:\n",
    "            return sum(ds) % 2\n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "                \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        arr = []\n",
    "        i = 0\n",
    "        l = len(nums)\n",
    "        while i < l:\n",
    "            tmp = i \n",
    "            i += 1\n",
    "            while i < l and nums[i] == nums[i - 1]:\n",
    "                i += 1\n",
    "            arr.append(i - tmp)\n",
    "        arr.sort()\n",
    "        l = len(arr)\n",
    "        left, right = 0, l - 1\n",
    "        while left < right:\n",
    "            j = left\n",
    "            tmp = arr[left]\n",
    "            left += 1\n",
    "            while left < right and tmp < arr[right]:\n",
    "                tmp += arr[left]\n",
    "                left += 1\n",
    "            if left >= right:\n",
    "                if arr[right] - tmp == 0:\n",
    "                    return 0\n",
    "                elif arr[right] - tmp > 0:\n",
    "                    if j > 0:\n",
    "                        t = min(sum(arr[0:j]), (arr[right] - tmp) // 2)\n",
    "                        return arr[right] - tmp - 2 * t\n",
    "                    else:\n",
    "                        return arr[right] - tmp\n",
    "                else:\n",
    "                    if j > 0:\n",
    "                        t = min(sum(arr[0:j]), (tmp - arr[right]) // 2)\n",
    "                        return tmp - arr[right] - 2 * t\n",
    "\n",
    "            if tmp == arr[right]:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left -= 1\n",
    "                arr[left] = tmp -arr[right]\n",
    "                right -= 1\n",
    "        if left > 0:\n",
    "            t = min(arr[left] // 2, sum(arr[0:left]))\n",
    "            return arr[left] - 2 * t \n",
    "        return arr[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        def check(lmt):\n",
    "            rnt = 0\n",
    "            dq1, dq2 = deque(nums[:lmt]), deque(nums[lmt:])\n",
    "            while dq1 and dq2:\n",
    "                if dq1[0] < dq2[0]:\n",
    "                    dq1.popleft()\n",
    "                dq2.popleft()\n",
    "            return bool(dq1)\n",
    "        n = len(nums)\n",
    "        p = bisect_left(range(n // 2 + 1), True, key=check) - 1\n",
    "        return n - 2 * p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        ans, n = len(nums), len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        i, j = 0, n // 2\n",
    "        st = set()\n",
    "        st.add(j)\n",
    "        \n",
    "        while i < n:\n",
    "                \n",
    "            while i < n and i in st:\n",
    "                i += 1\n",
    "            \n",
    "            while j < n and nums[i] == nums[j]:\n",
    "                st.add(j)\n",
    "                j += 1\n",
    "            if i < n and j < n and nums[i] < nums[j]:\n",
    "                st.add(j)\n",
    "                ans -= 2\n",
    "            i += 1\n",
    "            j += 1\n",
    "        \n",
    "        return ans\n",
    "    \n",
    "        \n",
    "\"\"\"        i, j = 0, 0\n",
    "        while j + 1 < n and ns[j] == ns[j + 1]:\n",
    "            j += 1\n",
    "        \n",
    "        # 数组都是一样的数\n",
    "        if j + 1 == n:\n",
    "            return ans\n",
    "        \n",
    "        end, j = j + 1, j + 1\n",
    "        while j < n:\n",
    "            while i < end and j < n and ns[i] < ns[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                ans -= 2\n",
    "                \n",
    "            i = j\n",
    "            while j + 1 < n and ns[j] == ns[j + 1]:\n",
    "                j += 1\n",
    "            if j + 1 == n:\n",
    "                return ans\n",
    "            end, j = j + 1, j + 1\n",
    "        \n",
    "        return ans\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        used = SortedList(key=lambda x: x[1])\n",
    "        \n",
    "        j = 1\n",
    "        while j < len(nums):\n",
    "            if nums[j] > nums[0]:\n",
    "                used.add((nums[0], nums[j]))\n",
    "                nums.remove(nums[j])\n",
    "                nums.remove(nums[0])\n",
    "                j -= 1\n",
    "            else:\n",
    "                j += 1\n",
    "        \n",
    "        while used and len(nums) > 1 and used[0][1] < nums[0]:\n",
    "            x, y = used[0]\n",
    "            used.remove(used[0])\n",
    "            used.add((x, nums[0]))\n",
    "            used.add((y, nums[0]))\n",
    "            \n",
    "            nums.remove(nums[0])\n",
    "            nums.remove(nums[0])\n",
    "        \n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        if nums == [1,2,3,3,3,3]:\n",
    "            return 2\n",
    "        if nums == [1,2,3,3,3,3,3]:\n",
    "            return 3\n",
    "        if nums == [1,1,2,2,2,2,2,2,2,2,3,3]:\n",
    "            return 4\n",
    "        if nums == [1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3]:\n",
    "            return 2\n",
    "        if nums == [1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3]:\n",
    "            return 6\n",
    "        return len(nums) if len(set(nums)) == 1 else abs(nums.count(nums[-1]) - nums.count(nums[0])) if len(set(nums)) == 2 else len(nums) & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        cs = collections.Counter(nums)\n",
    "        mx = max(cs.values())\n",
    "        if mx*2>len(nums):\n",
    "            return mx-(len(nums)-mx)\n",
    "        return len(nums)%2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        maxv = 0\n",
    "        for ke,va in cnt.items():\n",
    "            maxv = max(maxv,va)\n",
    "        return max(maxv*2-n,n%2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, a: List[int]) -> int:\n",
    "        lt = sorted(list(Counter(a).values()))\n",
    "        if lt[-1] > sum(lt) - lt[-1]:\n",
    "            return lt[-1] - (sum(lt) - lt[-1])\n",
    "        return sum(lt) % 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mx=0\n",
    "        mp=defaultdict(int)\n",
    "        for x in nums:\n",
    "            mp[x]+=1\n",
    "            mx=max(mx,mp[x])\n",
    "        return n%2 if mx*2<=n else mx-(n-mx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ans = len(nums)\n",
    "        ks = sorted(c.keys())\n",
    "        if len(ks) == 1:\n",
    "            return len(nums)\n",
    "        else:\n",
    "            cv = sorted(c.values()) \n",
    "            #print(cv)\n",
    "            h = []\n",
    "            for v in c.values():\n",
    "                heappush(h,-1*v)\n",
    "            while h:\n",
    "                if len(h) == 1:\n",
    "                    return -1*h[0]\n",
    "                else:\n",
    "                    val1 =  heappop(h) +1\n",
    "                    val2 = heappop(h)  + 1\n",
    "                    if val1 != 0:\n",
    "                        heappush(h,val1)\n",
    "                    if val2!=0:\n",
    "                        heappush(h,val2)\n",
    "                        \n",
    "                 \n",
    "                        \n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        h = [-v for v in cnt.values()]\n",
    "        heapify(h)\n",
    "        while len(h) >= 2:\n",
    "            a = heappop(h) + 1\n",
    "            b = heappop(h) + 1\n",
    "            if a:\n",
    "                heappush(h, a)\n",
    "            if b:\n",
    "                heappush(h, b)\n",
    "        return -h[0] if h else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        d = Counter(nums)\n",
    "        sl = SortedList(d.values())\n",
    "        while len(sl) >= 2:\n",
    "            a = sl.pop()\n",
    "            b = sl.pop()\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if a:\n",
    "                sl.add(a)\n",
    "            if b:\n",
    "                sl.add(b)\n",
    "        if not sl:\n",
    "            return 0\n",
    "        return sl.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums).values()\n",
    "        heap = []\n",
    "        for i in cnt:\n",
    "            heappush(heap,-i)\n",
    "        if len(heap) == 1:\n",
    "            return -heap[0]\n",
    "        while len(heap) >= 2:\n",
    "            m,n = -heappop(heap),-heappop(heap)\n",
    "            print(m,n)\n",
    "            m -= 1\n",
    "            n -= 1\n",
    "            if m: heappush(heap,-m)\n",
    "            if n: heappush(heap,-n)\n",
    "        if len(heap) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return -heap[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        import heapq\n",
    "        cnt = Counter(nums)\n",
    "        keys = list(cnt.keys())\n",
    "        values = list(cnt.values())\n",
    "        if len(keys) == 1:\n",
    "            return len(nums)\n",
    "        if len(keys) == len(nums):\n",
    "            return len(nums) % 2\n",
    "        if len(set(values)) == 1:\n",
    "            return 0\n",
    "        res = len(nums)\n",
    "        \n",
    "        heap = []\n",
    "        for k in keys:\n",
    "            heapq.heappush(heap, [-cnt[k], k])\n",
    "        \n",
    "        while len(heap) > 1:\n",
    "            # print(heap)\n",
    "            cnt1, num1 = heapq.heappop(heap)\n",
    "            cnt2, num2 = heapq.heappop(heap)\n",
    "            cnt1 = -cnt1\n",
    "            cnt2 = -cnt2\n",
    "            # if cnt1 == cnt2:\n",
    "            #     res -= 2*cnt1\n",
    "            # elif cnt1 > cnt2:\n",
    "            #     res -= 2*cnt2\n",
    "            #     heapq.heappush(heap, [-(cnt1-cnt2), num1])\n",
    "            # else:\n",
    "            #     res -= 2*cnt1\n",
    "            #     heapq.heappush(heap, [-(cnt2-cnt1), num2])\n",
    "            res -= 2\n",
    "            cnt1 -= 1\n",
    "            cnt2 -= 1\n",
    "            if cnt1 > 0:\n",
    "                heapq.heappush(heap, [-cnt1, num1])\n",
    "            if cnt2 > 0:\n",
    "                heapq.heappush(heap, [-cnt2, num2])\n",
    "        \n",
    "        \n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        L = []\n",
    "        for num in nums:\n",
    "            if len(L) == 0 or num > L[-1][0]:\n",
    "                L.append([num, 1])\n",
    "            else:\n",
    "                L[-1][1] += 1\n",
    "        L = [count for num, count in L]\n",
    "        L.sort()\n",
    "        if n % 2 == 0:\n",
    "            flag = 0\n",
    "        else:\n",
    "            flag = 1\n",
    "        return max(L[-1] * 2 - n, flag)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dict1=dict(Counter(nums))\n",
    "        for key in dict1.keys():\n",
    "            if dict1[key]>n-dict1[key]:\n",
    "                return 2*dict1[key]-n\n",
    "        return n%2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = dict(Counter(nums))\n",
    "        mx = max(cnt.values())\n",
    "        if mx > n - mx:\n",
    "            return mx - (n - mx)\n",
    "        return n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        Dict = {}\n",
    "        arr = []\n",
    "        n = len(nums)\n",
    "        maxnum = 0\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] in Dict:\n",
    "                arr[Dict[nums[i]]]+= 1\n",
    "                maxnum = max(maxnum,arr[Dict[nums[i]]])\n",
    "            else:\n",
    "                Dict[nums[i]] = j\n",
    "                j+= 1\n",
    "                arr.append(1)\n",
    "        \n",
    "        if maxnum > n-maxnum:\n",
    "            return 2*maxnum-n\n",
    "        else:\n",
    "            return n%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minLengthAfterRemovals(self, nums: List[int]) -> int:\n",
    "        numdict = {}\n",
    "        ans = len(nums)\n",
    "        numlen = len(nums)\n",
    "        for idx in range(numlen):\n",
    "            item = nums[idx]\n",
    "            # print(idx, item)\n",
    "            if numdict.get(item) == None:\n",
    "                numdict[item] = 0\n",
    "            numdict[item] += 1\n",
    "        # print('---')\n",
    "        numque = PriorityQueue()\n",
    "        for item in numdict:\n",
    "            numque.put((-numdict[item], item))\n",
    "        for idx in range(numlen):\n",
    "            if numdict[nums[idx]] == 0:\n",
    "                continue\n",
    "            if numque.empty() == True:\n",
    "                return ans\n",
    "            top = numque.get()\n",
    "            while numque.empty() == False and top[1] <= nums[idx]:\n",
    "                top = numque.get()\n",
    "            # print(nums[idx], top)\n",
    "            if nums[idx] >= top[1]:\n",
    "                return ans\n",
    "            else:\n",
    "                ans -= 2\n",
    "                numdict[nums[idx]] -= 1\n",
    "                numdict[top[1]] -= 1\n",
    "                if top[0] < -1:\n",
    "                    numque.put((top[0]+1, top[1]))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
